package com.likeycy.my.heap;

import com.likeycy.my.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * @ClassName: BinaryHeap
 * @Description: 二叉堆的逻辑结构就是一颗完全二叉树，所以也叫做完全二叉堆。当前默认实现最大堆
 * @Author: sodagreen
 * @Date: 2021/3/27 2:17
 * @Version: 1.0
 */
@SuppressWarnings("unchecked")
public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {

    private E[] elements;


    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 主要初始化构造函数
     * @param elements
     * @param comparator
     */
    public BinaryHeap(E[] elements, Comparator<E> comparator) {
        super(comparator);

        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
            size = elements.length;
            this.elements = (E[]) new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            heapify();
        }
    }

    public BinaryHeap(E[] elements) {
        this(elements, null);
    }


    public BinaryHeap() {
        this(null, null);
    }

    public BinaryHeap(Comparator<E> comparator) {
        this(null, comparator);
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullChecked(element);
        ensureCapacity(size + 1);

        elements[size] = element;
        size++;
        siftUp(size-1);
    }

    @Override
    public E get() {
        emptyChecked();
        return elements[0];
    }

    @Override
    public E remove() {
        emptyChecked();
        // 获取数组最后一个索引，并提前将size--操作
        int lastIndex = --size;
        E topElement = elements[0];
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;
        siftDown(0);

        return topElement;
    }

    @Override
    public E replace(E element) {
        elementNotNullChecked(element);
        // 首先判断sizes是否等于0，等于直接添加返回null
        if (size == 0) {
            elements[0] = element;
            size++;
            return null;
        }
        E oldTopElement = elements[0];
        elements[0] = element;
        siftDown(0);
        return oldTopElement;
    }

    /**
     * 批量建堆
     */
    private void heapify() {
        // 两种方式批量建堆
        // 1.自上而下的上滤
        /*for (int i = 1; i < size; i++) {
            siftUp(i);
        }*/

        // 2.自下而上的下滤，采取这种方法性能最好
        for (int i = (size >> 1) -1; i >= 0; i--) {
            siftDown(i);
        }


    }

    /**
     * 让指定索引位置的元素 下滤
     * @param index
     */
    private void siftDown(int index) {
        E curRootElement = elements[index];
        // 等同于 size除以2。右移一位表示除以2，右移两位表示除以2的平方，以此类推
        // 这里是计算非叶子节点数量。二叉堆的叶子节点的索引 == 非叶子节点的数量。公式为 floor(n/2)
        int half = size >> 1;
        // 找到第一个叶子节点后，那么往后的每个索引都是叶子节点。
        // 必须保证 index 位置是非叶子节点。这是因为非叶子节点才有左右子节点，而叶子节点是没有子节点的
        while (index < half) {
              // index有两种情况：
              // 1.只有单一一个左子节点
              // 2.有完整的左右子节点

            // 默认为左子节点跟它进行比较。左移一位等同于乘以2，左移两位等同于乘以2的平方，以此类推
            int leftChildIndex = (index << 1) + 1;
            E leftChildElement = elements[leftChildIndex];
            // 右子节点 (index << 1) + 2 == (index << 1) + 1 + 1
            int rightChildIndex = leftChildIndex + 1;

            // 选出左右子节点最大的那个
            if (rightChildIndex < size
                    && compare(elements[rightChildIndex], leftChildElement) > 0) {
                leftChildIndex = rightChildIndex;
                leftChildElement = elements[rightChildIndex];
            }

            // 这里处理第一种情况
            if (compare(curRootElement, leftChildElement) >= 0) {
                break;
            }

            // 执行到此处表示子节点大于根节点的值
            // 将子节点的值放到 index 位置
            elements[index] = leftChildElement;
            // 重新设置 index
            index = leftChildIndex;
        }
        elements[index] = curRootElement;

    }

    /**
     * 让指定索引位置的元素 上滤。未优化版本
     * @param index
     */
    private void siftUp1(int index) {
        E curElement = elements[index];
        while (index > 0) {
            // 获取当前索引的父节点。>> 1表示右移一位，等同于除以1个2。
            // 计算父节点的公式为 索引位 - 1 除以 2，如果有小数点，则向下取整。可以认为是去除小数点数，只取整数
            int parentIndex = (index -1) >> 1;
            E parentElement = elements[parentIndex];
            // 如果当前索引位置的值和父节点的值比较，是 小于等于0 的。那么直接返回，因为父节点和自己一样大，没必要交换
            if (compare(curElement, parentElement) <= 0) {
                return;
            }

            // 来到这里，表示当前索引的值大于父节点的值。按照最大堆性质，大的值在上层，子节点应该比父节点的值小或者相等
            // 所以这里需要交换 index 和 parentIndex位置的内容
            E temp = elements[index];
            elements[index] = elements[parentIndex];
            elements[parentIndex] = temp;
            // 重新赋值 index
            index = parentIndex;
        }
    }

    /**
     * 让指定索引位置的元素 上滤。优化交换版本
     * @param index
     */
    private void siftUp(int index) {
        E curElement = elements[index];
        while (index > 0) {
            // 获取当前索引的父节点。>> 1表示右移一位，等同于除以1个2。
            // 计算父节点的公式为 索引位 - 1 除以 2，如果有小数点，则向下取整。可以认为是去除小数点数，只取整数
            int parentIndex = (index -1) >> 1;
            E parentElement = elements[parentIndex];
            // 如果当前索引位置的值和父节点的值比较，是 小于等于0 的。那么直接返回，因为父节点和自己一样大，没必要交换
            if (compare(curElement, parentElement) <= 0) {
                break;
            }

            // 来到这里，表示当前索引的值大于父节点的值。按照最大堆性质，大的值在上层，子节点应该比父节点的值小或者相等
            // 将父元素存储在 index 位置
            elements[index] = parentElement;
            // 重新赋值 index
            index = parentIndex;
        }
        elements[index] = curElement;
    }



    /**
     * 扩容
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) {
            return;
        }
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

    private void emptyChecked() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("Heap is empty");
        }
    }

    /**
     * 检查元素是否为空
     * @param element
     */
    private void elementNotNullChecked(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        Integer index = (Integer) node;
        //  等同于 2 * index + 1
        index = (index << 1) + 1;
        return index >= size ? null : index;
    }

    @Override
    public Object right(Object node) {
        Integer index = (Integer) node;
        //  等同于 2 * index + 2
        index = (index << 1) + 2;
        return index >= size ? null : index;
    }

    @Override
    public Object string(Object node) {
        return elements[(int)node];
    }
}
